package style.Leetcode.初级算法.array.array_20221010_2_全排列;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 46.全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 * 输入：nums = [1]
 * 输出：[[1]]
 */
public class Solution {
    /**
     * 思路：回溯算法
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        // 初始化 HashMap ， key 为 num ， value 为该数字是否已停用
        // value 为 false 表示该数字未被使用
        HashMap<Integer, Boolean> visitedMap = new HashMap<>(nums.length);
        for (int num : nums) {
            visitedMap.put(num, false);
        }
        backtrack(nums, result, visitedMap, new LinkedList<>());
        return result;
    }

    /**
     * 回溯法 【状态重置】 【暴力搜索的变种算法】
     */
    private void backtrack(int[] nums,
                           List<List<Integer>> result,
                           HashMap<Integer, Boolean> visitedMap,
                           LinkedList<Integer> list) {
        // 判断 List 是否已经达到满足答案的长度
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }

        // 开始遍历数组数字
        for (int num : nums) {
            // 去哈希表中检查当前数字是否已使用
            // false 表示该数字未被使用
            if (!visitedMap.get(num)) {
                // 将当前数字添加到 list 中
                list.addLast(num);
                // 更新哈希表中关于该数字的使用状态
                visitedMap.put(num, true);
                // 再次进行 backtrack ，以当前数字为基础进行排列
                backtrack(nums, result, visitedMap, list);
                // 当结束上面的 backtrack 时，说明基于当前数字进行的回溯已经结束
                // 移除 list 中的元素
                // 因为 List 存放的是数字，所以不能直接使用 num 进行删除，否则调用的是另外一个重载方法
                list.removeLast();
                visitedMap.put(num, false);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.permute(new int[]{1, 2, 3, 4});
        System.out.println(lists.toString());

    }
}
